1. Field of the Invention
In general, the present invention relates to methods for locating objects from measurements of distances and travel times of signals. It also relates to methods in sequential estimation.
2. Description of Prior Art
Hyperbolic locations are typically derived by intersecting hyperboloids from estimates of the differences in distances between a primary point and pairs of stations located in space. The technique has numerous applications including the Global Positioning System, systems to locate cell phones, systems to locate calling animals, sonar systems used in the Navy, systems to locate lightening, underwater navigation systems, algorithms to locate earthquakes from seismic recordings, systems to locate aircraft using electromagnetic signals, systems to locate aircrafts, missiles, and ground equipment from their acoustic emissions, systems for locating electromagnetic emissions in general including radar and communication systems, and Positron Emission Tomography (PET) for the medical field.
Probability distributions for location have been estimated by either assuming that the variables, such as signal speed and station location, are linearly related to the location of the primary point (Chestnut, IEEE Transactions on Aerospace and Electronic Systems, Vol AES-18, No. 2, 214–218, 1982; Dailey and Bell, IEEE Transactions on Aerospace and Electronic Systems, Vol. 32 No. 3, p. 1148–1154, 1996; Wahlberg, Mohl, and Madsen, J. Acoustical Society America, Vol. 109, 397–406, 2001) or that the differences in distances are Gaussian random variables (Abel, IEEE Transactions on Aerospace and Electronic Systems, Vol. 26, No. 2, 423–426, 1990). Both assumptions are often invalid even though they are widely used. For example, the difference in distance is mathematically equal to the difference in distance between the primary point and each station. If the initial estimates of the station's locations are Gaussian random variables, then the difference in distance is also a random variable, but it is not Gaussian as approximated in prior art (Abel, 1990). It would be useful to be able to estimate probability distributions for primary points using realistic probability distributions for station coordinates, such as truncated Gaussian or uniform distributions.
Furthermore, hyperbolic locations are restricted to the case where the speed of signal propagation is constant throughout space, in which case the difference in distance is estimated from the difference in propagation time of the signal. But there are many situations in which the speed of the signal is not constant between a primary point and different stations. Examples of this occur in Global Positioning Systems (GPS), acoustic propagation in the sea, acoustic propagation in the Earth, mixed propagation cases where a signal propagates through different medium such as water and Earth, etc. U.S. Pat. No. 6,028,823 by Vincent and Hu titled “GEODETIC POSITION ESTIMATION FOR UNDERWATER ACOUSTIC SENSORS,” generalize hyperbolic location to one in which the speed of sound is restricted to a function of depth only in the sea. Non-linear equations are solved for location with an iterative linearization based on a Newton-Raphson method. One of the inventors says that it is not possible to solve the equations analytically, so an iterative procedure is used (Vincent, Ph.D thesis, Models, Algorithms, and Measurements for Underwater Acoustic Positioning, U. Rhode Island, p. 25, 2001). He says that this iterative least squares technique “suffers from several well known disadvantages such as (1) an initial guess of object position is required to linearize the systems of equations by expansion as a truncated Taylor series, (2) the procedure is iterative, (3) convergence is not guaranteed, and (4) the procedure has a relatively high computational burden” (Vincent, p. 25 2001). The procedure in U.S. Pat. No. 6,028,823 does not provide a method for solving for location when the speed of propagation varies in more than one Cartesian coordinate or when the variation in speed in not pre-computed as a function of one Cartesian coordinate (U.S. Pat. No. 6,388,948, Vincent and Hu). But there are many situations when the speed of the signal is not known ahead of time and also when the speed of propagation varies in more than one spatial coordinate both in the sea and in other environments. The method in U.S. Pat. No. 6,028,823 does not provide a means to solve these types of problems which commonly occur in GPS systems and even for systems for locating objects via their sounds in the sea, air, or Earth.
There appears to be another technical difficulty in estimating location errors even when one accounts for the fact that the linear approximation is invalid. When one has more than the minimum number of stations required to locate an object, the method for assessing errors does not appear to have been dealt with in the literature in a satisfying method. Schmidt's paper (Schmidt, IEEE Transactions on Aerospace and Electronic Systems, Vol. AES-8, No. 6, 821–835, 1972), uses Monte Carlo simulations to estimate maximum location errors of a primary point. Suppose for the moment that a mathematically unambiguous location can be achieved with three stations for a two-dimensional geometry. Schmidt jiggles ideal travel time differences and station coordinates within their expected errors to see how much a location changes with respect to the correct location. Errors are obtained by taking the largest misfit between the jiggled and correct estimate of location. When there are more than three stations, say , he suggests using this procedure for each combination of three stations giving,
            (                                    ℛ                                                3                              )        =                  ℛ        !                                          (                          ℛ              -              3                        )                    !                ⁢                  3          !                      ,total combinations. Each combination is referred to as a “constellation” here. Schmidt suggests using a least squares procedure to find a final estimate of error from the results of the largest misfit from each constellation. He does not prove this least-squares procedure is optimal, and indeeds states that he is not sure of any advantages in using a least-squares procedure in this situation.
There does not appear to be a practical method for estimating probability distributions for hyperbolic location for the overdetermined problem mentioned by Schmidt (1972) when the distributions for station locations and estimates of differences of distance are not Gaussian random variables.
Bayes theorem provides a method to compute the probability distribution for location but it requires an enormous number of computations to implement. Suppose one wants the joint probability density function, ƒ({right arrow over (s)}, {right arrow over (r)}, {right arrow over (c)}|τij), of the source location, {right arrow over (s)}, receiver locations, {right arrow over (r)}, and speeds of propagation between the source and each receiver, {right arrow over (c)}, given a measurement of the difference in propagation time between the source and receivers i and j, τij. Bayes theorem supplies the desired result,
                                          f            ⁡                          (                                                s                  →                                ,                                  r                  →                                ,                                                      c                    →                                    ❘                                      τ                                          i                      ⁢                                                                                          ⁢                      j                                                                                  )                                =                                                    f                ⁡                                  (                                                                                    τ                                                  i                          ⁢                                                                                                          ⁢                          j                                                                    ❘                                              s                        →                                                              ,                                          r                      →                                        ,                                          c                      →                                                        )                                            ⁢                              π                ⁡                                  (                                                            s                      →                                        ,                                          r                      →                                        ,                                          c                      →                                                        )                                                                                    ∫                                                      f                    ⁡                                          (                                                                                                    τ                                                          i                              ⁢                                                                                                                          ⁢                              j                                                                                ❘                                                      s                            →                                                                          ,                                                  r                          →                                                ,                                                  c                          →                                                                    )                                                        ⁢                                      π                    ⁡                                          (                                                                        s                          →                                                ,                                                  r                          →                                                ,                                                  c                          →                                                                    )                                                        ⁢                                      ⅆ                                          s                      →                                                        ⁢                                      ⅆ                                          r                      →                                                        ⁢                                      ⅆ                                          c                      →                                                                                  ⁢                                                                                  ,                            (        1        )            in terms of the conditional probability, ƒ(τij|{right arrow over (s)}, {right arrow over (r)}, {right arrow over (c)}), of obtaining the data, τij, given the locations of the source and receivers, and speeds of propagation, and in terms of the prior joint distribution, π({right arrow over (s)}, {right arrow over (r)}, {right arrow over (c)}). If the distributions on the right side could be evaluated analytically, then evaluating Eq. (1) would possibly provide a practical solution to the problem. One could introduce new data, and keep finding better estimates of the distribution on the left given updated distributions on the right. It appears difficult to find analytical solutions for the distributions on the right because the variables are related in nonlinear ways from which progress appears to be at a standstill. Brute force evaluation of the distributions on the right also appears computationally impractical because of the high dimensionality of the joint distributions. In hyperbolic location, for example, for R receivers, there are three variables for the Cartesian coordinates of the source and each receiver, as well as a speed of propagation making a total of 3+3R+1=3R+4 variables. For R=5, one would need to estimate the joint probability density functions of 19 variables, for each introduced datum (a 19 dimensional space). Suppose each variable is divided into ten bins. Accurate estimation of the joint distribution requires a reliable probability of occurrence in 1019 bins in the example given above. Since this is not practical to compute, Bayes theorem does not offer a practical means to compute probability distributions of location for many cases of interest.
It is useful to be able to estimate probability distributions for variables of interest that occur in non-linear situations or when a priori distributions are not Gaussian. The location of a primary point from measurements of the difference in arrival time at two or more stations is an example of a nonlinear problem when variables may not be described as being Gaussian. When variables are Gaussian, a Kalman filter can be used to estimate their probability distributions (Gelb, Applied Optimal Estimation, p. 105–107, M.I.T. Press, Cambridge, Mass. 1996). When the Kalman filter is not applicable to a problem, one can attempt to find solutions by linearizing equations and iterating to optimize an objective function. This approach may not converge to the correct solution if the initial guess is not close to the correct answer. There is a need for a procedure to estimate probability distributions for non-linear systems or for systems in which the variables are not Gaussian.
For ellipsoidal locations, there does not appear to be a method for obtaining probability distributions for the primary point when using the sums of distances or the sums of travel times between two points and a primary point without making a linear approximation or without assuming some or all of the variables are Gaussian random variables. Furthermore, when one uses measurements of travel time to estimate the sums of distances, ellipsoidal location methods assume that the speed of propagation is constant. Ellipsoidal locations are strictly invalid when the speed of propagation varies between the stations. It would be useful to have a method to obtain locations when the speeds of propagation are not the same between each instrument.
There do not appear to be methods to estimate probability distributions for initially unknown locations of a primary point and for locations of the stations and the speed of propagation without recourse to linearizing approximations and assumptions of Gaussian distributions. For example, Dosso and Collison (Journal of the Acoustical Society of America, Vol. 111, 2166–2177, 2002) linearize equations between underwater station locations and the location of a acoustic source in a problem dealing with hyperbolic location. They assume the location of the source is approximately known and that prior probability distributions for the data and locations of source and stations are Gaussian. But it would be useful to have a robust method to estimate these distributions without recourse to Gaussian statistics and without making a linear approximation, which may be inaccurate and which may lead to a solution in a non-global minimum of a cost function.